package queue.homework;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 使用栈实现队列
 * 栈：入栈出栈在同一端
 * 队列：队首出队，队尾入队
 * 入队和入栈等同
 * 出队，需要移除栈底元素，使用另外一个栈存放第一个栈出栈后的元素
 */

class MyQueue {
    private Deque<Integer> stack;
    private int front;//追踪栈首元素

    public MyQueue() {
        stack = new LinkedList<>();
        front = 0;
    }

    /**
     * 将栈顶看作队尾，则入队操作等同于入栈操作
     * O(1)
     *
     * @param x
     */
    public void push(int x) {
        //如果没有出栈操作，则栈首元素就是第一次入栈的元素
        if (stack.isEmpty()) front = x;
        stack.push(x);

    }

    /**
     * 栈顶是队尾，那么栈底就是队首了
     * 要移除栈底元素，要让栈内元素全部出栈，
     * 使用一个新栈，通过入栈存放旧栈出栈元素
     * 等到移除栈底元素后，将新栈内的元素出栈并入栈到旧栈中
     * O（n）
     *
     * @return
     */
    public int pop() {
        Deque<Integer> stack2 = new LinkedList<>();
        while (stack.size() > 1) {
            front = stack.peek();
            stack2.push(stack.pop());
        }
        int ret = stack.pop();
        //队首即新栈的栈首元素
        while (stack2.size() > 0) {
            stack.push(stack2.pop());
        }
        return ret;
    }

    public int peek() {
        return front;
    }

    public boolean empty() {
        return stack.isEmpty();
    }
}
